package com.gemini.main.sort;

import java.util.Arrays;

public class MergeSort {

    public static void mergeSort(int[] a) {
        int length = a.length;
        mergeSort0(a, 0, length - 1);
    }

    private static void mergeSort0(int[] arr, int start, int end) {
        if (start >= end) return;
        int mid = (start + end) / 2;
        // 分治递归
        mergeSort0(arr, start, mid);
        mergeSort0(arr, mid + 1, end);

        //merge
        merge(arr, start, mid, end);
    }


    private static void merge(int[] arr, int start, int mid, int end) {
        int i = start, j = mid + 1, k = 0;
        int[] temp = new int[end-start+1];// temp 数组应该为当前拷贝进来的数组的长度
        //前++是先自加再使用而后++是先使用再自加
        while (i <= mid && j <= end) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }

        // 把左边剩余的数移入数组
        while (i <= mid) {
            temp[k++] = arr[i++];
        }
        // 把右边边剩余的数移入数组
        while (j <= end) {
            temp[k++] = arr[j++];
        }
        // 把新数组中的数覆盖nums数组
        for (int x = 0; x < temp.length; x++) {
            arr[x + start] = temp[x];
        }


    }

    public static void main(String[] args) {
        int[] arr = {1, 4, 3, 5, 2, 0};
        mergeSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
